package algorithm.Linked;

import java.util.HashMap;

/**
 * 复制 含有随机节点的额链表
 */
public class CopyLinked {

    private class Node {
        public int value;
        public Node next;
        public Node rand;

        public Node(int value) {
            this.value = value;
        }
    }

    public Node copyListWithRand1(Node head) {
        HashMap<Node, Node> map = new HashMap<>();
        Node cur = head;
        while(cur != null) {
            map.put(cur, new Node(cur.value));
            cur = cur.next;
        }

        cur = head;
        while (cur != null) {
            map.get(cur).next = cur.next;
            map.get(cur).rand = cur.rand;
            cur = cur.next;
        }
        return map.get(head);
    }

    public Node copyListWithRand2(Node head) {
        if (head == null) {
            return null;
        }

        Node cur = head;
        Node next;
        while (cur != null) {
            Node copyCur = new Node(cur.value);
            copyCur.next = cur.next;
            cur.next = copyCur;
            cur = copyCur.next;
        }

        cur = head;
        Node copyNode;
        while (cur != null) {
            copyNode = cur.next;
            copyNode.rand = cur.rand.next;

            cur = copyNode.next;
        }

        Node res = head.next;
        cur = res;
        while (cur != null) {
            head.next = cur.next;
            head = cur.next;

            cur.next = head.next;
            cur = head.next;
        }

        return res;
    }
}
